from typing import List

MOD = 10 ** 9 + 7


class Solution:
    def profitableSchemes(self, n: int, p: int, group: List[int], profit: List[int]) -> int:
        groups = [(group[i], profit[i]) for i in range(len(group))]
        groups.sort()
        size = len(groups)

        def dfs(i, nn, pp):
            if i == size:
                if pp <= 0:
                    return 1
                else:
                    return 0

            else:
                res = 0
                res += dfs(i + 1, nn, pp)  # 不完成当前任务
                if nn >= groups[i][0]:
                    res += dfs(i + 1, nn - groups[i][0], pp - groups[i][1])  # 完成当前任务
                return res % MOD

        return dfs(0, n, p)


if __name__ == "__main__":
    print(Solution().profitableSchemes(n=5, p=3, group=[2, 2], profit=[2, 3]))  # 2
    print(Solution().profitableSchemes(n=10, p=5, group=[2, 3, 5], profit=[6, 7, 8]))  # 7

    # 测试用例3
    print(Solution().profitableSchemes(n=1, p=1, group=[2, 2, 2, 2, 2], profit=[1, 2, 1, 1, 0]))  # 0
